﻿using System.Collections.Generic;

namespace System
{
	public delegate TKey BSTKeyFunc<TKey, TObj>(TObj Object);
	public class BST<TKey, TObj>
		where TKey : IComparable
	{
		public TKey NodeID;
		public TObj Data;
		public int Depth;

		public BST<TKey, TObj> Left;
		public BST<TKey, TObj> Right;
		public BST<TKey, TObj> Parent;

		public BST(TKey id, TObj data, BST<TKey, TObj> parent)
		{
			NodeID = id;
			Data = data;
			Left = null;
			Right = null;
			Parent = parent;
			Depth = 0;
			SetDepth();
		}
		public void Clear()
		{
			Left = null;
			Right = null;
			GC.Collect();
		}
		public void SetDepth()
		{
			if (Left != null)
				Left.SetDepth();
			if (Right != null)
				Right.SetDepth();
			int N1 = Left == null ? -1 : Left.Depth;
			int N2 = Right == null ? -1 : Right.Depth;
			Depth = Math.Max(N1, N2) + 1;
		}
		void ResetDepth()
		{
			BST<TKey, TObj> Current = this;
			while (Current != null)
			{
				BST<TKey, TObj> Par = Current.Parent;
				if (Par != null)
				{
					int N1 = Par.Left == null ? -1 : Par.Left.Depth;
					int N2 = Par.Right == null ? -1 : Par.Right.Depth;
					Par.Depth = Math.Max(N1, N2) + 1;
				}
				Current = Parent;
			}
		}

		public TObj this[TKey ID]
		{
			get
			{
				return SearchData(ID);
			}
		}
		public BST<TKey, TObj> Search(TKey ID)
		{
			BST<TKey, TObj> Res = this;
			bool Finished = false;
			while (!Finished)
			{
				int N = Res.NodeID.CompareTo(ID);
				if (N == 0)
					Finished = true;
				else if (N < 0)
				{
					if (Res.Right == null)
					{
						Res = null;
						Finished = true;
					}
					else
						Res = Res.Right;
				}
				else if (N > 0)
				{
					if (Res.Left == null)
					{
						Res = null;
						Finished = true;
					}
					else
						Res = Res.Left;
				}
			}
			return Res;
		}
		public TObj SearchData(TKey ID)
		{
			BST<TKey, TObj> Node = Search(ID);
			if (Node == null)
				return default(TObj);
			return Node.Data;
		}

		static void buildbst<TSKey, TSObj>(ref BST<TSKey, TSObj> Target, BST<TSKey, TSObj> Parent, List<TSObj> Objects, BSTKeyFunc<TSKey, TSObj> KeyFetcher, int N1, int N2)
			where TSKey : IComparable
		{
			int N = (N1 + N2) / 2;
			TSObj O = Objects[N];
			Target = new BST<TSKey, TSObj>(KeyFetcher(O), O, Parent);
			int N3 = N - 1;
			int N4 = N + 1;
			//Left
			if (N1 < N3)
				buildbst(ref Target.Left, Target, Objects, KeyFetcher, N1, N3);
			else if (N1 == N3)
				Target.Left = new BST<TSKey, TSObj>(KeyFetcher(Objects[N1]), Objects[N1], Target);
			//Right
			if (N4 < N2)
				buildbst(ref Target.Right, Target, Objects, KeyFetcher, N4, N2);
			else if (N4 == N2)
				Target.Right = new BST<TSKey, TSObj>(KeyFetcher(Objects[N2]), Objects[N2], Target);
		}
		public static void BuildBST<TSKey, TSObj>(ref BST<TSKey, TSObj> Target, List<TSObj> Objects, Comparison<TSObj> Sorter, BSTKeyFunc<TSKey, TSObj> KeyFetcher)
			where TSKey : TKey
			where TSObj : TObj
		{
			if (Objects.Count == 0)
				Target = null;
			else
			{
				Objects.Sort(Sorter);
				buildbst(ref Target, null, Objects, KeyFetcher, 0, Objects.Count - 1);
			}
		}
	}
}